1. Field of the Invention
The present invention generally relates to computer systems employing a dedicated graphics display processor and, in particular, to a robust apparatus and methodology eminently suited for implementation in a computer graphics co-processor for the non-ambiguous procedural filling of complex polygons in graphics display memory.
2. Description of the Related Art
In modestly to highly sophisticated computer systems, there is a desire to relieve the main computer or host processor of many time consuming, specialized and generally invariant processing tasks. For example, such tasks may include parallel/serial/parallel communication protocol conversions and the hardware control procedures required in the support of a physical hard disk drive. Consequently, various computer co-processors have been developed to support dedicated functions such as serial communications and mass storage control. As a result, the host is allowed to deal with such functions at a high level of abstraction.
The support of graphic display functions is another area of co-processor application. Conventionally, a dedicated graphics memory area is provided within the host computer system. At least a portion of this graphic display memory is mapped to a graphics display, typically a very high resolution CRT. The graphics display co-processor is typically implemented to accept high level commands, such as draw.sub.-- line (x.sub.1 y.sub.1, x.sub.2 y.sub.2), draw.sub.-- circle (xy, r) and draw.sub.-- box (x.sub.1 y.sub.1, x.sub.2 y.sub.2, x.sub.3 y.sub.3, x.sub.4 y.sub.4). These high level instructions and the data provided with them, are processed by the graphics co-processor to convert x and y numerical values to a series of corresponding pixel locations and then to memory addresses of data storage locations within the graphic display memory. Often the graphics co-processor will further provide for the periodic reading of the graphic display memory to refresh the corresponding image presented on the CRT. Thus, even a simple high level instruction such as draw.sub.-- line (x.sub.1 y.sub.1, x.sub.2 y.sub.2) can result in thousands of memory access operations on the graphics display memory, depending on the length of the line and the resolution of its representation within the graphics display memory.
Conventionally, a problem occurs in the handling of a high level instruction that directs the filling of a polygon. A fill instruction is one of the most complex high level instructions that could reasonably be supported by a graphics co-processor. The instruction, effectively accompanied by a list of the vertices of a specific polygon to be filled, initiates co-processor procedures that include selecting sets of three vertices from those of the polygon and then performing respective triangle area fills. The triangle fill is typically by an implementation of the Bresenham algorithm. This algorithm utilizes the calculable slope of two sides of the triangle, as known from its three vertices, as the basis for sequentially selecting the beginning and ending pixel locations of a fill line generally one pixel in width. The fill line is effectively drawn in the graphic display memory by the writing of data into corresponding memory locations. Thus, a line by line filling of the triangle occurs with new beginning and ending pixels locations being interpolated for each fill line.
While the Bresenham algorithm provides a reliable methodology for filling triangles, the fill polygon instruction, when directed against a wide variety of complex polygons, will encounter an ambiguity that cannot be handled by a conventional graphics co-processor. That is, polygons that present concave boundaries, possess self-intersecting boundaries, have self-overlapping sections or contain a fully enclosed "hole" have not been found to be accurately filled by simple decomposition to sets of triangles that are, in turn, filled. For example, a triangle sharing two vertices of the concave portion and any third vertex of a polygon is indeterminate as to whether it or any portion thereof should be filled.
A similar, additional ambiguity is encountered when considering a section of a complex polygon that is either self-overlapped or represents a "hole". That is, an ambiguity arises in determining whether to fill that portion of the polygon or not. This determination is further required in order to properly represent the overlap distinct from the remainder of the filled polygon. Often, it is desirable to represent an overlapped area of a polygon by a corresponding area of high-intensity brightness or a distinguishable color.
Consequently, many graphics co-processors either make no attempt to implement a complex polygon fill instruction or premise the utilization of the instruction on a non-complex polygon. In computer systems employing such graphics co-processors, the host is therefore required to manage the fill operation in close detail and ascertain by whatever faculties are at its disposal whether areas adjacent boundaries of the complex polygon are to be filled and, further, whether high intensity fill, representative of overlapping or double fill, is appropriate.